Saltar a contenido

📘 Clase 08: Recursividad y Programación Dinámica con Memoización

Open In Colab Abrir en Studio Local Ver en GitHub

1. 💡 Fundamentación Teórica y Modelo Mental

Optimización exponencial $O(2^N)$ a lineal $O(N)$ mediante subproblemas superpuestos: 1. Subestructura Óptima: La solución global se compone de las soluciones óptimas de sus partes. 2. Memoización (Top-Down): Almacenar en caché (dict o @lru_cache) los resultados ya computados. 3. Tabulación (Bottom-Up): Construir la tabla de soluciones de forma iterativa desde el caso base.

🌟 Modelo Mental de la Sesión: «Las Muñecas Rusas y el Bloc de Notas de Resultados»

En esta sesión anclamos el aprendizaje en la metáfora del mundo real para visualizar cómo fluyen las estructuras de datos y el flujo de ejecución en la memoria.

2. 🗺️ Arquitectura de Ejecución y Diagrama de Flujo

flowchart TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3) [📦 Cached]"]
    B --> D["fib(3)"]
    B --> E["fib(2) [📦 Cached]"]
    D --> F["fib(2)"]
    D --> G["fib(1)"]
    style A fill:#1e293b,color:#ffffff,stroke:#3b82f6,stroke-width:2px
    style C fill:#059669,color:#ffffff,stroke:#34d399,stroke-width:2px
    style E fill:#059669,color:#ffffff,stroke:#34d399,stroke-width:2px

3. 💻 Código de Implementación Práctica

```python from functools import lru_cache

@lru_cache(maxsize=None) def fibonacci(n: int) -> int: if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2)

print("Fibonacci(50) en microsegundos:", fibonacci(50)) ```

```python def fib_bottom_up(n: int) -> int: if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b

print("Fib(10):", fib_bottom_up(10)) ```

4. 🛡️ Buenas Prácticas PEP 8: Antipatrones vs Código Pythonic

⚠️ Cuidado con los Antipatrones

def contar(n):
if n == 0: return 0
return contar(n - 1)  # ❌ Falla con n > 1000 por RecursionError

```python

Enfoque iterativo (Bottom-Up) o sys.setrecursionlimit

def contar_iterativo(n): return sum(range(n)) # ✅ O(1) memoria ```

5. 🏋️ Desafío Práctico de la Clase

🎯 Enunciado del Reto

Crea una función fibonacci_dinamico(n: int) -> int que calcule el n-ésimo número de Fibonacci en tiempo $O(N)$ utilizando programación dinámica o memoización.

⚡ Resolución Híbrida en 1 Clic (Local + Web)

Si tienes ejecutando wisrovi ui en tu terminal local, puedes 🚀 Abrir este Reto directamente en tu Studio Local (127.0.0.1:8501) para escribir tu código con auto-formateo AST, inspeccionar variables en el Heap/Stack y evaluarlo con pruebas en tiempo real.

def fibonacci_dinamico(n: int) -> int:
# ✍️ Implementa Fibonacci en O(N) sin recomputar
if n <= 0:
    return 0
if n == 1:
    return 1
a, b = 0, 1
for _ in range(2, n + 1):
    a, b = b, a + b
return b
💡 Pista Socrática 1

💡 Pista 1: Puedes usar un enfoque iterativo con dos variables a = 0, b = 1.

💡 Pista Socrática 2

💡 Pista 2: En un bucle de 2 a n + 1, actualiza a, b = b, a + b.

💡 Pista Socrática 3

💡 Pista 3: Retorna b al finalizar el bucle.

Para resolver este ejercicio en tu entorno: 1. Abre el archivo ejercicios/reto.py de esta clase en Visual Studio Code o utiliza wisrovi ui / wisrovi tutor. 2. Implementa tu solución cumpliendo los requisitos y contratos de tipado. 3. Valida tus resultados ejecutando las pruebas unitarias: 

pytest tests/curso_02/test_clase_08_recursividad_y_programacion_dinamica.py

6. 📚 Fuentes y Bibliografía Recomendada